#ifndef GRAPH_H_
#define GRAPH_H_

#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>

using LinkId = int;
using NodeId = int;
using FlowId = int;

const int kMaxValue = 10000000;
const std::vector<int>Omega = {1, 2, 3};  //全部可用资源
const int limit_cost = 8;

struct Node{
    NodeId node_id;
    int node_type; //0代表红色节点(不可开启)，1代表蓝色节点(高延迟)，2代表黑色节点(低延迟)
};

struct Link
{
    Link(LinkId link_id_in, int link_state_in,NodeId source_id_in, NodeId ter_id_in,
         int cost_in, int delay_in, std::vector<int> A_units_in)
        : link_id(link_id_in), link_state(link_state_in),source_id(source_id_in),
          ter_id(ter_id_in), cost(cost_in), delay(delay_in), A_units(A_units_in)
    {
        weight = 0;
        used = false;
    }
    ~Link()
    {
    }
    LinkId link_id;
    int link_state; //0表示未开启，1为开启高延迟，2为开启低延迟
    NodeId source_id;
    NodeId ter_id;
    int cost;
    int delay;
    std::vector<int> A_units; //该线路上可用资源
    int weight;
    bool used;
};

struct Path
{
    Path(NodeId i=-1)
    {
        cost = kMaxValue;
        delay = kMaxValue;
        C_units = Omega;
        curNode=i;
        path_info.reserve(50);
    }

    void clear()
    {
        path_info.clear();
        cost = kMaxValue;
        delay = kMaxValue;
        C_units = Omega;
    }

    void Print() const{
        for(NodeId i:path_info){
            std::cout<<i<<"  ";
        }
        std::cout<<std::endl;
    };

    bool find(NodeId id)
    {
        if (node_set.empty())
        {
            for (NodeId node : path_info)
            {
                node_set.insert(node);
            }
        }
        return (node_set.find(id) != node_set.end());
    }

    friend bool operator<(const Path &a, const Path &b)
    {
        return a.cost < b.cost;
    }
    friend bool operator>(const Path &a, const Path &b)
    {
        return a.cost > b.cost;
    }

    std::vector<NodeId> path_info;
    std::vector<Link *> path_link;
    NodeId curNode;
    int cost;
    int delay;
    std::vector<int> C_units; // 该路径上使用的资源

private:
    std::unordered_set<NodeId> node_set;
};


struct Lable{
    int weight;  //可以是cost,也可以是delay
    LinkId Edge_id;
    int Edge_state;
    std::vector<int> CU;  //使用的资源

    Lable(){}
    Lable(int weight_in, LinkId Edge_id_in, int Edge_state_in,std::vector<int> CU_in):
    weight(weight_in), Edge_id(Edge_id_in), Edge_state(Edge_state_in),CU(CU_in){}
};
const Lable l_0 = {0, 0, 0,Omega};

class Graph
{
public:
    explicit Graph(int size) : size_(size), node_to_egress_links_(size,std::vector<Link*>{}),
        node_to_ingress_links_(size,std::vector<Link*>{}), nodes_type_(size) {
        links_.reserve(size_ * size_ * 10);
        links_black_.reserve(size_ * size_ * 10);
        links_blue_.reserve(size_*size_*10);
    }

    void addNodes(NodeId id, int type){
        if(id > size_){
            return;
        }
        nodes_.insert(id);
        nodes_type_[id-1] = type;
    }

    void addLinks(LinkId link_id,NodeId source_id, NodeId ter_id,
         double cost, double delay, std::vector<int> A_units ){
            if(source_id>size_||ter_id>size_){
                return;
            }
            links_.emplace_back(link_id, 0, source_id, ter_id, cost, delay, A_units);
            int type = nodes_type_[ter_id-1];
            if(type==2){
                links_black_.emplace_back(link_id, 2, source_id,  ter_id, -1, delay+10, A_units);
            }else if(type==1){
                links_blue_.emplace_back(link_id, 1, source_id,  ter_id, -1, delay+100, A_units);
            }
         }
    
    //构建节点未开启时的Graph
    void makeGraph0(){
        for(int i = 0; i<links_.size();i++){
            Link* link = &links_[i];
            NodeId ter = link->ter_id;
            NodeId source = link->source_id;
            LinkId id = link->link_id;
            node_to_egress_links_[source-1].emplace_back(link);
            node_to_ingress_links_[ter-1].emplace_back(link);
            id_to_links_.insert(std::pair<LinkId,Link*>(id, link));
            
        }
    }


    //构建低延迟节点开启后的Graph
    void makeGraph2(){
        for(int i = 0; i<links_black_.size();i++){
            Link* link = &links_black_[i];
            NodeId ter = link->ter_id;
            NodeId source = link->source_id;
            node_to_egress_links_[source-1].emplace_back(link);
            node_to_ingress_links_[ter-1].emplace_back(link);
        }
    }

    //构建高延迟节点开启后的Graph
    void makeGraph1(){
        for(int i = 0; i<links_blue_.size();i++){
            Link* link = &links_blue_[i];
            NodeId ter = link->ter_id;
            NodeId source = link->source_id;
            node_to_egress_links_[source-1].emplace_back(link);
            node_to_ingress_links_[ter-1].emplace_back(link);
        }
    }

    void Check(){
        std::cout<<node_to_egress_links_[6][1]->cost<<"\n";
        std::cout<<nodes_type_[7];
    }


    int NodeSize() const
    {
        return size_;
    }

    int LinkSize() const
    {
        return links_.size();
    }

    void SortLinks();

   std::vector<Link *> GetEgressLinks(
        NodeId node) const
    {
        return node_to_egress_links_.at(node-1);
    }

    std::vector<Link *> GetIngressLinks(
        NodeId node)
    {
        return node_to_ingress_links_.at(node);
    }
    
    Link * GetIdLinks(LinkId id) 
    {
        auto iter = id_to_links_.find(id);
        if(iter!=id_to_links_.end()){
        return iter->second;
        } 
        return nullptr;
    }


    Link *FindLink(int from, int to)
    {
        std::vector<Link *> &tmp = node_to_egress_links_.at(from);
        for (int i = 0; i < tmp.size(); ++i)
        {
            if (tmp[i]->ter_id == to)
                return tmp[i];
        }
        return nullptr;
    }

    int GetNodeType(NodeId n){
        return nodes_type_[n-1];
    }
    

private:
    std::vector<Link> links_; //记录所有未开启节点的边
    std::vector<Link> links_black_; //记录开启低延迟节点的边
    std::vector<Link> links_blue_; //记录开启高延迟节点的边
    std::unordered_set<NodeId> nodes_;
    std::vector<int> nodes_type_; // 记录不同节点的类型
    //std::vector<std::vector<Link *>> node_to_egress_links_;
    std::vector<std::vector<Link *>> node_to_ingress_links_;
    std::vector<std::vector<Link *>> node_to_egress_links_;
    std::unordered_map<LinkId, Link*> id_to_links_; //由id查找link
 
    int size_;
    Graph(const Graph &) = delete;
    Graph &operator=(const Graph &) = delete;
};

struct Flow
{
    Flow() {}
    Flow(FlowId id_in, NodeId from_in, NodeId to_in) : id(id_in), from(from_in), to(to_in){}
    void Print() const;
    FlowId id;
    NodeId from;
    NodeId to;
};

class Demand
{
public:
    // Read network flows from a file.
    explicit Demand(const std::string &file_path);

    int NumFlows()
    {
        return flows_.size();
    }
    const Flow &GetFlow(FlowId id)
    {
        return flows_.at(id);
    }

private:
    std::vector<Flow> flows_;
};

#endif // GRAPH_H_
